/*
** pack bins(rectangle or cube) inside a container(rectangle or cube)
** This is for initializing positins of tiles, for which we use bounding boxes to appximate.
** The algorithm is subject to improvement or modification.
*/

#ifndef _BIN_PACKING_H_
#define _BIN_PACKING_H_

#include <vector>
#include <list>
#include <algorithm>
#include <iterator>

//CGAL
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/bounding_box.h>

#include "containers.h"

namespace Packing_common
{
	/*
	** packing 2D bins
	** very naive algorithm, subject to improvement
	** assume the bottom of the container is fixed
	*/
	class Bin_packing_2
	{
		
		typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
		
		/* **********************************************************************************
		** platform segments
		** horizontal segments on which a new bin can be placed
		*/
		struct H_seg 
		{
			double left;
			double right;
			double height;

			H_seg(double l, double r, double h) : left(l), right(r), height(h) { }

			double length() const { return right-left; }

			bool contain(double l, double r) const // whether it can hold a segment
			{
				return length()>=(r-l);
			}
		};

		typedef std::list<H_seg>::iterator H_seg_iter;
		typedef std::list<H_seg>::const_iterator Con_H_seg_iter;

		// sort platform segments according to y coordinate
		struct y_order_cmp : public std::binary_function<H_seg_iter, H_seg_iter, bool>
		{
			bool operator()(Con_H_seg_iter seg0, Con_H_seg_iter seg1) const
			{
				return seg0->height < seg1->height;
			}
		};
		// sort platform segments according to x coordinate
		struct x_order_cmp : public std::binary_function<H_seg_iter, H_seg_iter, bool>
		{
			bool operator()(Con_H_seg_iter seg0, Con_H_seg_iter seg1) const
			{
				return seg0->left < seg1->left;
			}
		};
		/*****************************************************************************************/

	public:

		typedef CGAL::Iso_rectangle_2<K> Iso_rectangle_2;

	public:

		Bin_packing_2(const Rectangular_box& container) ;

		/* 
		** put one bin inside and return its position
		** the order in which bins are put depends on the caller
		*/
		bool put_one_bin(const Iso_rectangle_2& bin, double& pos_x, double& pos_y) ;

		void clear() ;

	private:

		// merge possible platforms with the same height
		bool merge() ; 
		
		// lift up the lowest platform, the standard height is the second lowest platform
		bool liftup() ; 

	private:
		const Rectangular_box& box;
		std::list<H_seg> terrace;
		std::list<H_seg_iter> x_sorted;
		std::list<H_seg_iter> y_sorted;

		// cutting off container height, to prevent some bins being too high
		double cut_height;
	};

	
}

#endif